package searcher;
import java.util.*;

/**
 * got from internet
 * @author shitgao
 *
 * @param <Type>
 */
abstract public class Heap<Type extends Comparable<Type>> implements
Iterable<Type> {
private ArrayList<Type> container = new ArrayList<Type>();

private boolean sorted = false;
private boolean big;

// 交换
private void swap(int i, int j) {
Type temp = this.container.get(i);
container.set(i, this.container.get(j));
container.set(j, temp);
}

protected void setBig() {
this.big = true;
}

protected void setLittle() {
this.big = false;
}

// 计算父节点的index
protected static int getParent(int index) {
if (index < 0) {
 return -2;
} else if (index == 0) {
 return -1;
} else {
 return (index - 1) / 2;
}
}

// 计算左子节点
protected static int getLeft(int index) {
return ((index + 1) << 1) - 1;
}

// 计算右子节点
protected static int getRight(int index) {
return ((index + 1) << 1);
}

// i的子树(l and r)都是有序堆，调整i使它有序
protected void Heapify(int i, int size) {
int l = Heap.getLeft(i);
int r = Heap.getRight(i);
int key;
ArrayList<Type> A = container;

if (l < size
  && (((A.get(l).compareTo(A.get(i)) > 0) && this.big) || ((A
    .get(l).compareTo(A.get(i)) < 0) && !this.big))) {
 key = l;
} else {
 key = i;
}

if (r < size
  && (((A.get(r).compareTo(A.get(key)) > 0) && this.big) || ((A
    .get(r).compareTo(A.get(key)) < 0) && !this.big))) {
 key = r;
}

if (key != i) {
 swap(i, key);
 this.Heapify(key, size);
}
}

// 建成堆
protected void Build() {
for (int i = this.size() / 2 - 1; i >= 0; i--) {
 this.Heapify(i, this.size());
}
}

// 排序
protected void sort() {
if (!this.sorted) {
 // 建成堆
 this.Build();
 // 排序
 for (int size = this.size() - 1; size > 0; size--) {
  swap(size, 0);
  this.Heapify(0, size);
 }
 // 翻转元素，使container升序排列
 Collections.reverse(this.container);
 this.sorted = true;
}
}

public int size() {
return this.container.size();
}

protected void showContainer() {
System.out.println("----------------");
if (this.big) {
 System.out.println("big");
} else {
 System.out.println("little");
}
for (Type e : this.container) {
 System.out.println(e);
}
System.out.println("----------------");
}

// 加入元素
public void add(Type e) {
this.container.add(e);
this.sorted = false;
}

//added by shitgao 
public void addWithOrder(Type e){
	int pos=container.size();
	int parent;
	boolean flag=true;
	container.add(e);
	while (pos>0 && flag){
		parent=Heap.getParent(pos);
		if ((this.big && container.get(pos).compareTo(container.get(parent))>0) ||
				((!this.big) && container.get(pos).compareTo(container.get(parent))<0)){
			swap(pos,parent);
			pos=parent;
		}
		else
			flag=false;
	}
}
//added by shitgao
public Type removeWithOrder(){
	if (container.size()==0)
		return null;
	Type e =container.get(0);
	swap(container.size()-1,0);
	container.remove(container.size()-1);
	Heapify(0,size());
	return e;
}

public Iterator<Type> iterator() {
sort();
return this.container.iterator();
}
}
